package code;


public class SortedArrayToBst {

	static public class TreeNode{
		int val;
		TreeNode left;
		TreeNode right;
		TreeNode(int x){
			val=x;
		}
	}
	static public class ListNode{
		int val;
		ListNode next;
		ListNode(int x){
			val=x;
		}
	}
	public void travser(TreeNode root){
		System.out.println(root.val);
		if(root.left!=null)
			travser(root.left);
		if(root.right!=null)
			travser(root.right);
	}
	public TreeNode buildTree(int[] A,int l,int r){
		if(l==r)
		{
			return new TreeNode(A[l]);
		}
		int mid=l+r>>1;
		TreeNode p=new TreeNode(A[mid]);
		if(mid>l)
			p.left=buildTree(A,l,mid-1);
		p.right=buildTree(A,mid+1,r);
		return p;
	}
	

	public TreeNode solved(int[] A){
		
		int i,j;
		int n=A.length;
		TreeNode root=null;
		root=buildTree(A,0,n-1);
		travser(root);
		return root;
	}
	
    public TreeNode sortedListToBST(ListNode head) {
    	if(head==null)
    		return null;
    	ListNode p=head;
    	int n=0;
    	while(p!=null){
    		n++;
    		p=p.next;
    	}
    	int[] A=new int[n];
    	p=head;
    	int i=0;
    	while(p!=null){
    		A[i++]=p.val;
    		p=p.next;
    	}
    	TreeNode root=null;
		root=buildTree(A,0,n-1);
		return root;
    }
	public static void main(String[] args){
		SortedArrayToBst satb=new SortedArrayToBst();
		int[] A={1};
		satb.solved(A);
	}
}
